package arithmetic2.day05;

import java.util.HashMap;
import java.util.Map;

/*
    题目：
        链表中的每一个节点有一个next指针，指向链表的下一个节点，有一个rand指针随机指向一个节点或者null
        给定一个这样的链表，编写一个方法将该链表复制一份
 */
public class List {
    private Node head;  //头结点
    private int size;   //大小

    public List() {
    }

    public List(Node head) {
        this.head = head;
    }

    //添加节点
    public void add(int value) {
        if (head == null) {
            head = new Node(value);
            size++;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(value);
        size++;
    }

    //复制一份链表返回，使用hash表
    public List copy() {
        if (this.size < 1) {
            return new List();
        }
        Map<Node, Node> map = new HashMap();
        //遍历链表
        Node temp = head;
        while (temp != null) {
            map.put(temp, new Node(temp.value));
            temp = temp.next;
        }
        //遍历map集合
        for (Node n : map.keySet()) {
            map.get(n).next = map.get(n.next);
            map.get(n).rand = map.get(n.rand);
        }
        //根新链表设置头结点
        return new List(map.get(head));
    }

    //复制一份链表返回，不使用hash表
    public List copy2() {
        if (this.size < 1) {
            return new List();
        }
        //遍历链表，将每一个复制的节点放在原先的节点的后面
        Node temp = head;
        while (temp != null) {
            //创建一个克隆节点,值为当前节点的值
            Node node = new Node(temp.value);
            //将克隆节点放在当前节点后面
            node.next = temp.next;
            temp.next = node;
            //指针后移两个
            temp = temp.next.next;
        }
        //重置指针，重新遍历链表，为克隆节点的rand赋值
        temp = head;
        while (temp != null) {
            //为当前节点的克隆节点的rand属性赋值
            temp.next.rand = temp.rand != null ? temp.rand.next : null;
            //指针后移两个
            temp = temp.next.next;
        }
        //使用newHead来保存新链表的头节点
        Node newHead = head.next;
        //将两个链表拆开
        temp = head;
        Node temp1 = newHead;
        while (temp1.next != null) {
            temp.next = temp.next.next;
            temp1.next = temp1.next.next;
            temp = temp.next;
            temp1 = temp1.next;
        }
        temp.next = null;
        return new List(newHead);
    }

    //遍历链表
    public void print() {
        if (head != null) {
            Node temp = head;
            while (temp != null) {
                System.out.print(temp.value + " ");
                temp = temp.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        List list = new List();
        list.add(1);
        list.add(2);
        list.add(3);
        list.print();
//        List list1 = list.copy();
        List list1 = list.copy2();
        list1.print();
        list.print();

    }
}
